#include <iostream>
#include "s-clique_free.cpp"
#include "IO.cpp"
#include <vector>
#include <boost/dynamic_bitset.hpp>
#include <string>
#include <ctime>
using namespace std;

void bubble_desc(vector<edge>& edge_set)
{
    int flag = 1;
    int size = edge_set.size();       /** a színek száma **/
    edge e;
    for(int i = 1; (i <= size) && flag; i++) {
        flag = 0;
        for (int j = 0; j < (size -1); j++) {
            if (edge_set[j+1].c > edge_set[j].c) {
                e = edge_set[j];
                edge_set[j] = edge_set[j+1];
                edge_set[j+1] = e;
                flag = 1;
            }
        }
    }
}

void bubble_asc(vector<edge>& edge_set)
{
    int flag = 1;
    int size = edge_set.size();       /** a színek száma **/
    edge e;
    for(int i = 1; (i <= size) && flag; i++) {
        flag = 0;
        for (int j = 0; j < (size -1); j++) {
            if (edge_set[j+1].c < edge_set[j].c) {
                e = edge_set[j];
                edge_set[j] = edge_set[j+1];
                edge_set[j+1] = e;
                flag = 1;
            }
        }
    }
}

/**
 * Feljegyzi, hogy a színosztályban melyik élek mennyi klikket alkotnak.
 * Sorba végig megy a színosztályokon és ha talált két szomszédos csúcsot,
 * akkor megszámolja, hogy mennyi s-klikket alkot, ehhez a
 * clq_srch_count függvényt használja.
 * Ha az élhez egyetlen s-klikket sem talált, akkor azt az élt rögtön töröljük
 * a gráfból és a színosztályból is, hiszen az nem befolyásolja a feladatunkat,
 * azonban könnyítheti a további számolást, oly módon, hogy kevesebb él lesz
 * amivel számolni kell.
 **/
vector<edge> note_edges(vector<dynamic_bitset<> >& graph, dynamic_bitset<> color, int s)
{
    vector<edge> edge_set;
    int size = graph.size();
    size_t i, j;
    for(i = 0; i < size; i = color.find_next(i)) {
        if(color[i]) {
            for(j = i + 1 < size ? i +1 : size - 1; j < size; j = color.find_next(j)) {
                if(color[j] && graph[i][j]) {
                    int c = clq_search_count(graph, (graph[i] & graph[j] & color), s-2);
                    if(c == 0) {
                        graph[i][j] = 0;
                        graph[j][i] = 0;
                    } else {
                        struct edge e;
                        e.node_a = i;
                        e.node_b = j;
                        e.c = c;
                        edge_set.push_back(e);
                    }
                }
            }
        }
    }
    return edge_set;
}

vector<edge> delete_edges(vector<dynamic_bitset<> > graph, vector<dynamic_bitset<> > quasi_colorclasses, int s)
{
    int edge_set_size;
    int q_colors = quasi_colorclasses.size();
    vector<edge> edge_set;
    vector<edge> deleted_edges;

    for(int i = 0; i < q_colors; ++i){
        cout<<"color: "<<i<<endl;
        do {
            edge_set = note_edges(graph, quasi_colorclasses[i], s);
            bubble_desc(edge_set);
            edge_set_size = edge_set.size();

            if(edge_set_size > s) {
                int i = 0;
                do{
                    edge edge_to_delete = edge_set[i];
                    deleted_edges.push_back(edge_to_delete);
                    graph[edge_to_delete.node_a][edge_to_delete.node_b] = 0;
                    graph[edge_to_delete.node_b][edge_to_delete.node_a] = 0;
                    cout<<"edges: "<<edge_set_size<<" cliques: "<<edge_to_delete.c<<endl;
                    ++i;
                }while((edge_set[i].c == edge_set[i + 1].c || i < 10) && i < edge_set_size);
            }
            else if(edge_set_size > 1){
                edge edge_to_delete = edge_set[0];
                deleted_edges.push_back(edge_to_delete);
                graph[edge_to_delete.node_a][edge_to_delete.node_b] = 0;
                graph[edge_to_delete.node_b][edge_to_delete.node_a] = 0;
            }
        } while(edge_set_size > 0);
    }

    return deleted_edges;
}

int main(int argc, char** argv)
{

    if(argc != 4) {
        cout<<"Usage: ./filename 'graph_name' s - int k - int"<<endl;
        return 0;
    }

    int s = atoi(argv[2]);
    int k = atoi(argv[3]);
    if(s < 2) {
        cout<<"s must be a positive integer!"<<endl;
        return 0;
    }

    string filename( argv[1] );

    ofstream fout;
    fout.open("noteLogFile.log", ofstream::app);
    fout.seekp(0, fout.end);

    int nodes, edges;
    vector<dynamic_bitset<> > graph;
    readgraph_bitset(filename, graph, nodes, edges);

    vector<dynamic_bitset<> > colorclasses;
    loadcolors(colorclasses, filename, s, nodes);
    vector<dynamic_bitset<> > quasi_colorclasses = colorclasses;

    clock_t start = clock();
    cout<<"1"<<endl;
    reclassify(graph, quasi_colorclasses, k, s);
    vector<dynamic_bitset<> > quasi_colors = quasi_colorclasses;
    vector<edge> deleted_edges = delete_edges(graph, quasi_colorclasses, s);
    clock_t end = clock();

    cout<<"quasi colors: "<<quasi_colorclasses.size()<<endl;
    cout<<"edges to delete: "<<deleted_edges.size()<<endl;

    time_t rawtime;
    struct tm* timeinfo;
    char buffer[80];
    time (&rawtime);
    timeinfo = localtime(&rawtime);
    strftime(buffer,80,"%d-%m-%Y %I:%M:%S",timeinfo);
    string date(buffer);
    fout<<date<<" - Graph: "<<filename<<"\ts: "<<s<<"\tsolution of reclassify: ";
    fout<<quasi_colorclasses.size()<<"("<<quasi_colorclasses.size() * (s-1)<<")"<<"\tk: "<<k<<" noted edges: "<<deleted_edges.size();
    fout<<"\treclassify+note time: "<<diffclock(end, start)<<endl;

    save_checkpoint(graph, quasi_colors, filename + "_unsorted", s, k, deleted_edges);
    bubble_asc(deleted_edges);
    save_checkpoint(graph, quasi_colors, filename , s, k, deleted_edges);
    for(int i = 0; i < deleted_edges.size(); ++i)
        cout<<"i: "<<i<<" edge: "<<deleted_edges[i].node_a<<':'<<deleted_edges[i].node_b<<" c: "<<deleted_edges[i].c<<endl;
    return 0;
}
